#include <iostream>
#include <fstream>
#include "SortingConfig.h"

using namespace std;

void swap(int &a, int &b) {
    int t=a;
    a = b;
    b = t;
}

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int _val): val(_val), next(nullptr){};
};


void radix_sort_pos(int *arr, int n) {
    // 基数排序算法，要求输入元素均大于等于0
    int radix=10, R=10, r;
    ListNode *heads[radix]={nullptr};
    ListNode *tails[radix]={nullptr};
    // 根据待排序数组构建链表节点
    ListNode *nodes[n];
    for(int i=0; i<n; ++i) {
        nodes[i] = new ListNode(arr[i]);
    }

    bool flag;
    do {
        flag = false;
        // 将数组元素插入对应基数链表
        for(int i=0; i<n; ++i) {
            nodes[i]->val = arr[i];
            nodes[i]->next = nullptr;
            // 计算对应基数下的值
            r = arr[i] % R / (R/10);
            // 插入链表尾部
            if (!tails[r]) {
                tails[r] = nodes[i];
                heads[r] = nodes[i];
            } else {
                tails[r]->next = nodes[i];
                tails[r] = tails[r]->next;
            }
            // 判断是否还有元素值大于等于R，需要继续进行基数排序
            if (!flag && arr[i]>=R) flag = true;
        }
        // 按基数顺序依次取出链表元素，放入排序数组中
        int p=0;
        for (int r=0; r<radix; ++r) {
            // 从当前基数链表中依次取出元素，并放入排序数组中
            while (heads[r]) {
                arr[p] = heads[r]->val;
                heads[r] = heads[r]->next;
                p++;
            }
            tails[r] = nullptr;
        } 
        R *= radix;
    } while(flag);
    // 释放申请的内存
    for(int i=0; i<n; ++i) {
        delete nodes[i];
    }
}

void radix_sort(int *arr, int n) {
    // 基数排序算法
    int negNum=0;
    for(int i=0; i<n;++i) {
        if (arr[i] < 0) {
            if (i != negNum) swap(arr[negNum], arr[i]);
            // 将负数转换成正数
            arr[negNum] = -arr[negNum]-1;
            negNum ++;
        }
    }
    // 对负数部分进行基数排序;
    radix_sort_pos(arr, negNum);
    // 对非负数部分进行基数排序
    radix_sort_pos(arr+negNum, n-negNum);
    // 将负数还原并翻转顺序
    for(int i=0; i<negNum/2;++i) {
        arr[i] = -arr[i]-1;
        arr[negNum-i-1] = -arr[negNum-i-1]-1;
        swap(arr[i], arr[negNum-i-1]);
    }
    if (negNum%2==1) {
        arr[(int)(negNum/2)] = -arr[(int)(negNum/2)]-1;
    }
}

int main(int argc, char *argv[]) {
    cout << "Sorting Version: " << Sorting_VERSION_MAJOR 
         << "." << Sorting_VERSION_MINOR<<endl;
    // 参数解析
    ifstream input;
    if (argc > 1) {
        input.open(argv[1], ios::in);
    }

    int n;
    if (argc > 1) input >> n;
    else cin >> n;
    int arr[n];
    if (argc > 1){
        for(int i=0; i<n;++i) input >> arr[i];
        input.close();
    } else {
        for(int i=0; i<n;++i) cin >> arr[i];
    }
    // 排序
    radix_sort(arr, n);

    for(int i=0; i<n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}